package class05;

import java.util.Arrays;
import java.util.function.BooleanSupplier;

/**
 * <a href="https://leetcode.cn/problems/sort-an-array/">912. 排序数组</a>
 */
public class Code02_PartitionAndQuickSort {

    public static void swap(int[] arr, int L, int R) {
        int T = arr[L];
        arr[L] = arr[R];
        arr[R] = T;
    }

    // 快排 1.0 时间复杂度：O(N²)
    public static void quickSort1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int M = partition1(arr, L, R);
        quickSort1(arr, L, M - 1);
        quickSort1(arr, M + 1, R);
    }

    public static int partition1(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int lessRegion = L - 1;
        int index = L;
        while (index < R) {
            if (arr[index] <= arr[R]) {
                swap(arr, ++lessRegion, index);
            }
            ++index;
        }
        swap(arr, ++lessRegion, R);
        return lessRegion;
    }

    // 快排 2.0 时间复杂度：O(N²)
    public static void quickSort2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] M = partition2(arr, L, R);
        quickSort1(arr, L, M[0] - 1);
        quickSort1(arr, M[1] + 1, R);
    }

    public static int[] partition2(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int lessRegion = L - 1;
        int moreRegion = R;
        int index = L;
        while (index < moreRegion) {
            if (arr[index] < arr[R]) {
                swap(arr, ++lessRegion, index++);
            } else if (arr[index] > arr[R]) {
                swap(arr, --moreRegion, index);
            } else {
                ++index;
            }
        }
        swap(arr, moreRegion, R);
        return new int[]{lessRegion + 1, moreRegion};
    }

    // 快排 3.0 时间复杂度：O(N·log N)
    public static void quickSort3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] M = partition2(arr, L, R);
        quickSort1(arr, L, M[0] - 1);
        quickSort1(arr, M[1] + 1, R);
    }

    public static void main(String[] args) {
        for (int x = 0; x < 1_000; ++x) {
            int[] arr1 = new int[100];
            for (int i = 0; i < arr1.length; ++i) {
                arr1[i] = (int) (Math.random() * (100 - 1) + 1);
            }
            int[] arr2 = arr1.clone();
            quickSort3(arr1, 0, arr1.length - 1);
            Arrays.sort(arr2);
            for (int i = 0; i < arr1.length; ++i) {
                if (arr1[i] != arr2[i]) {
                    System.out.println("错误");
                }
            }
        }
    }

}
